The present invention relates to a stripe pattern matching system for verifying matching of a searching stripe pattern such as a fingerprint gathered from a field to a filed stripe pattern already registered in a file.
FIG. 2 is a pattern diagram illustrating minutiae of a fingerprint pattern by way of example of the stripe pattern.
A method for identifying a stripe pattern such as a fingerprint pattern is disclosed in a Japanese patent published with a specification No. 12674/'85, wherein end points such as those 2a to 2e of ridge lines 1a to 1e and bifucations such as a joining point 3a of two ridge lines 1f and 1g of FIG. 2 are defined as the minutiae to be used for the matching verification.
For each minutia, a direction and four relations are defined in addition to its X-Y coordinates.
First, direction D.sub.i of a minutia, the end point 2a of FIG. 2, for example, is defined as the orientation of the ridge line 1a starting from the concerning minutia 2a expressed relatively to horizontal X-axis. In case of a bifucation, the joining point 3a, for example, its direction is represented by the orientation of a valley line between joining two ridge lines 1f and 1g.
Then, talking notice of each individual minutia, the end point 2a, for example, as a mother minutia, all x-y plane is defined, which has its origin at the mother minutia 2a and its y-axis in the direction D.sub.i of the mother minutia. In each of four quadrants determined by the x-y plane, a minutia nearest to the origin, that is the mother minutia, is assigned to a child minutia in the quadrant, and numbers of ridge lines between the mother minutia 2a and the four child minutiae 2b, 2c, 3a and 2d are defined as four relations R1 to R4, respectively. In the example, the relation R1 of the minutia 2a is two, as there are two ridge lines, 1b and an extension of 1a, between the two end points 2a and 2b. In the same way, R2=1, R3=2 and R4=1. When there is an obscure part between a mother minutia and a child minutia, concerning relation Ri is represented as Ri=x.
Thus, a stripe pattern is represented by a list of minutiae, in the prior art.
In another Japanese patent published with a specification No. 21233/'88, there is disclosed a stripe pattern matching system making use of the minutia list for verifying matching of a searching stripe pattern to a filed stripe pattern.
As for matching of the stripe pattern such as the fingerprint, there are two ways of verification. One is a way applied for identifying an unknown searching finger print gathered from a field, by verifying its matching to one of a plurality of filed fingerprints already registered, such as performed for criminal investigation, and the other is a way applied for confirming an individual by verifying matching of his fingerprint input together with his ID number to a specific fingerprint registered accompanied by the ID number, such as applied to gate control.
FIG. 14 is a flowchart illustrating all example of the former way, and FIG. 15 is that of the latter way.
In the way of FIG. 14, after an area pattern and a minutia list of a searching stripe pattern are input (at step 47), those of a filed stripe pattern are input (at step 48). Then (at step 49), correspondence of each minutia registered in the minutia list of the searching stripe pattern is checked to each minutia registered in the minutia list of the filed stripe pattern by comparing their coordinates, directions and relations, for listing up pairs of minutiae, which are possibly corresponding to each other, into a candidate pair list as candidate pairs. Here, more than one candidate pair may be listed for one minutia of the searching stripe pattern. Then, coordinate adjustment values, that is, deviations of X-Y coordinates and direction between two corresponding minutiae are calculated for every candidate pair (at step 50) referring to the candidate pair list for checking distribution of the deviations. Processes performed at steps 49 and 50 are called the rough matching 61.
When significant coordinate adjustment values are found (at step 51) in distribution of the deviations, coordinates of minutiae of the searching stripe pattern listed in the candidate pair list are adjusted (at step 52) according to the significant coordinate adjustment values. Then (at step 53), each candidate pair is verified and selected by comparing coordinates and direction of the searching stripe pattern minutia after the coordinate adjustment with those of the filed stripe pattern. Then, correspondence value of each candidate pair after the selection is revised referring to correspondence between corresponding child minutiae of the paired minutiae (at step 54), considering the fact that when a pair of two mother minutiae have correspondence, each four pair of their child minutiae should have correspondence too.
Then (at step 55), a pair list of pairs, each composed of a minutia S.sub.i of the searching stripe pattern and its corresponding minutia F.sub.j, when there is, in the filed stripe pattern, is extracted from the candidate pair list referring to correspondence value thus revised, as follows. Among the candidate pairs, a pair having a maximum correspondence value is selected and listed in the pair list, and candidate pairs left in the candidate pair list and having either minutia of the pair listed in the pair list are rejected as false pairs. Then, a candidate pair having maximum correspondence value among the candidate pairs left in the revised candidate pair list is selected and listed in the pair list as a next pair. By repeating the above selection until all candidate pairs are extracted or rejected from the candidate pair list, the pair list is prepared, wherein a specific minutia of the searching stripe pattern or the filed stripe pattern is listed in only one pair in the pair list, and some minutiae are left unpaired.
Then (at step 56), correspondence value of each pair is again revised referring to corresponding values between corresponding child minutiae of the paired minutiae in a similar way with step 54, and the unpaired minutiae are checked whether it is significant or not by checking if their partner minutiae are to be found in ineffective pattern area or not, or if they are one of opposing minutiae or not. After thus revising the correspondence values, a matching value is calculated (at step 57) by normalizing sum of the correspondence values by number of effective minutiae.
When no significant coordinate adjustment value is found at step 51, control goes directly to step 57 attributing the matching value of zero to the concerning filed stripe pattern.
The processes performed from step 51 to step 57 are called a detailed matching 62.
Thus repeating the rough matching 61 and the detailed matching 62 from step 48 to 57 for every filed stripe pattern, an ID number of a filed stripe pattern giving a largest matching value is output (at step 58) at the end of the matching verification of FIG. 14.
In FIG. 15, on the other hand, wherein identification of a searching stripe pattern is confirmed, an ID number of a specific filed stripe pattern is input for the first (at step 59). Then, the same procedure with FIG. 14 from step 47 to step 57 is performed only once for the filed stripe pattern specified by the ID number. When the matching value obtained at step 57 is larger than a fixed level, the ID number is confirmed at step 60.
FIG. 16 is a flowchart illustrating processes performed in a criminal investigation for searching a filed stripe pattern having a set of minutiae {F.sub.j } (j=1, 2, . . . ) most similar to a set of minutiae {S.sub.i } (i=1, 2, . . . ) of a searching stripe pattern among a plurality of filed stripe patterns, that is, detailed processes of the way described in connection with FIG. 14.
Initializing both of a maximum matching value MSC and an ID number N of a most matching filed stripe pattern to zero, a set of minutiae {S.sub.i } is extracted from a searching stripe pattern S at step 71. Then, a set of minutia {F.sub.j } and an ID number n of a filed stripe pattern are read out at step 72. When there is no filed stripe pattern to be read out, control goes to step 85, and otherwise, control goes to step 73.
At step 73, each minutia F.sub.il (il.di-elect cons.j) of the filed stripe pattern having coordinates, direction and relations whereof differences are all within respective threshold values from those of a minutia S.sub.i of the searching stripe pattern is registered in the candidate pair list as a partner of the minutia S.sub.i of each of candidate pairs {S.sub.i : F.sub.il /v.sub.il } together with their correspondence value v.sub.il, which is performed for each minutia S.sub.i of the set of minutiae {S.sub.i }.
Thus, following candidate pairs are listed in the candidate pair list.
S.sub.1 : F.sub.11 /v.sub.11, S.sub.1 : F.sub.12 /v.sub.12, . . . , PA1 S.sub.i : F.sub.i1 /v.sub.i1, S.sub.i : F.sub.i2 /v.sub.12, . . . , PA1 S.sub.m : F.sub.m1 /v.sub.m1, S.sub.m : F.sub.m2 /v.sub.12, . . . , PA1 X.sub.i.sup.r =X.sub.i cos r+Y.sub.i sin r, PA1 Y.sub.i.sup.r =Y.sub.i cos r+X.sub.i sin r, PA1 D.sub.i.sup.r =D.sub.i +r. PA1 .DELTA.X.sub.i =X.sub.i -X.sub.il, PA1 .DELTA.Y.sub.i =Y.sub.i -Y.sub.il, PA1 .DELTA.D.sub.i =D.sub.i -D.sub.il ; PA1 a feature extraction means for extracting features of minutiae from the searching stripe pattern; PA1 a searching stripe pattern feature memory for storing the features extracted by the feature extraction means; PA1 a filed stripe pattern feature memory wherein prepared features of minutiae of the plurality of filed stripe patterns; PA1 a pairing examination means for evaluating a correspondence value between a minutia of the searching stripe pattern stored in the searching stripe pattern feature memory and a minutia of the filed stripe pattern prepared in the filed stripe pattern feature memory; PA1 a candidate pair list wherein candidate pairs are registered, each of said candidate pairs being a pair of a minutia of the searching stripe pattern and a minutia of the filed stripe pattern which are decided to be similar with each other by the pairing examination means evaluating the correspondence value between them; PA1 a coordinate conversion means for calculating rotated coordinates of each of minutiae of the searching stripe pattern by rotating coordinates of said each of minutiae by a rotation angle designated around a designated point of an X-Y plane wherewith the coordinates of said each of minutiae are defined; PA1 a rotated stripe pattern feature memory for storing the rotated coordinates of each of minutiae of the searching stripe pattern calculated by the coordinate conversion means to be accessed with each value of the rotation angle; PA1 a deviation plane memory for accumulating the correspondence value of each of the candidate pairs satisfying a nomination condition at an address thereof indicated by deviation coordinates of said each of the candidate pairs, the deviation coordinates being differences between the rotated coordinates of a minutia of the searching stripe pattern and coordinates of a minutia of the filed stripe pattern of said each of the candidate pairs; and PA1 a control means for, PA1 selecting axial candidates among the candidate pairs, PA1 obtaining concentrated deviation coordinates giving a largest accumulation of the correspondence value for each of the axial candidates by controlling the deviation plane memory to accumulate the correspondence value of each of the candidate pairs satisfying the nomination condition according to the deviation coordinates obtained from the rotated coordinates calculated by the coordinate conversion means with the rotation angle equivalent to a direction difference between two minutiae of said each of the axial candidates, PA1 finding a most appropriate axial candidate which gives a maximum value of the largest accumulation among the axial candidates, PA1 determining the direction difference and the concentrated deviation coordinates given by the most appropriate axial candidate as a most appropriate rotation angle and most appropriate shifting coordinates of the searching stripe pattern, respectively, and PA1 performing a detailed matching of the searching stripe pattern to the filed stripe pattern making use of the most appropriate rotation angle and the most appropriate shifting coordinates.
Then, a maximum concentration M, a most appropriate rotation angle R and most appropriate shifting coordinates (.DELTA.X, .DELTA.Y) are initialized to zero.
Then, a rotation angle r is initialized to -29.4.degree., for example, at step 74 and it is incremented by 1.4.degree. at step 75.
At step 76, X-Y coordinates and direction (X.sub.i, Y.sub.i, D.sub.i) of each minutia S.sub.i are rotated with the rotation angle r in relation to origin of the X-Y plane, for example, into rotated values (X.sub.i.sup.r, Y.sub.i.sup.r, D.sub.i.sup.r) as follows:
Then, calculating deviations (.DELTA.X.sub.i, .DELTA.Y.sub.i, .DELTA.D.sub.i) of rotated minutia S.sub.i.sup.r from its partner minutia F.sub.il having coordinates and direction (X.sub.il, Y.sub.il, D.sub.il) as follows:
correspondence value v.sub.il of each candidate pair is accumulated on a discrete .DELTA.X-.DELTA.Y deviation plane, when direction deviation .DELTA.D.sub.i is within a threshold value TD.
After all correspondence values {v.sub.il } are accumulated on corresponding coordinates of the discrete .DELTA.X-.DELTA.Y deviation plane, concentrated deviation coordinates (.DELTA.X', .DELTA.Y') having a largest accumulation M' of the correspondence values {v.sub.il } are obtained for the concerning rotation angle r, and, at step 77, the maximum concentration M, the most appropriate rotation angle R and the most appropriate shifting coordinates (.DELTA.X, .DELTA.Y) are replaced with the largest accumulation M', the concerning rotation angle r and the concentrated deviation coordinates (.DELTA.X', .DELTA.Y'), respectively, when the largest accumulation M' is larger than the maximum concentration M.
Then, at step 78, it is checked whether the rotation angle r is smaller than 28.0.degree., for example, and steps 75 to 78 are repeated by incrementing the rotation angle r with 1.4.degree. until it attains to 28.0.degree..
Thus, the maximum concentration M, the most appropriate rotation angle R and the most appropriate shifting coordinates (.DELTA.X, .DELTA.Y) of the searching stripe pattern are obtained for a concerning filed stripe pattern.
When the maximum concentration M is found smaller than a fixed value at step 79, matching value SC of the concerning filed stripe pattern is set to zero (at step 80) considering there is no significant correspondence thereto, and the control returns to step 72 for verifying correspondence to a next filed stripe pattern.
When the maximum concentration M is larger than the fixed value, the control goes to step 81 for performing the detailed matching.
At step 81, coordinates and direction of every of the set of minutiae {S.sub.i } are adjusted by applying the most appropriate rotation angle R and the most appropriate shifting coordinates (.DELTA.X, .DELTA.Y) as the adjustment values into a set of adjusted minutiae {S.sub.i }.
At step 82, candidate pairs {S.sub.i : F.sub.il /vil} are calculated in the same way as performed at step 73 making use of the set of adjusted minutiae {S.sub.i } instead of the original set of minutiae {S.sub.i }. Then at step 83, a pair list is extracted by rejecting duplicated candidate pairs, each correspondence value of the listed pair is reinforced or omitted, and a normalized sum of the correspondence values is calculated as the matching value SC of the searching stripe pattern to the concerning filed stripe pattern, as described previously in connection with respective steps 54, 55, 56 and 57 of FIG. 14.
When the matching value SC is larger than the maximum matchimg value MSC, the maximum matching value MSC is substituted with the matching value SC and the ID number n of the concerning filed stripe pattern is assigned to the ID number N of the most matching filed stripe pattern at step 84.
Then, the control is returned to step 72, for repeating processes from step 72 to step 84 until there is found no filed stripe pattern to be read out.
Finally at step 85, the maximum matching value MSC thus revised is compared with a threshold value. When the maximum matching value MSC is larger than the threshold value, the ID number N is output as the ID number of the most matching filed stripe pattern, and otherwise, it is reported that there is found no filed stripe pattern matching to the searching stripe pattern S.
As above described, matching procedure disclosed in the Japanese patent of the specification No. 21233/'88 is performed on an assumption that the set of minutiae {S.sub.i } or {F.sub.j } of the searching or the filed fingerprint, when it is the case, is represented by coordinates and direction relative to the X-Y plane which have origin approximately at the core of the fingerprint and Y-axis approximately oriented to the fingertip. Based on the assumption, candidate pairs are sought at step 73 of FIG. 16, and at steps 74 to 78, coordinates adjustment is performed referring to correspondence between paired minutiae. Therefore, pairing at step 73 plays an important role, and once minutiae are paired inadequately because of low quality of a partly gathered fingerprint or lack of core of a fingerprint in the cases such as a plain arch pattern, it is very difficult to adjust their coordinates, needing to reset again the origin and the direction, or needing to prepare several different coordinate planes for the correct matching.
This is a problem of the prior art.
In a Japanese patent application laid open as a Provisional Publication No. 183380/'90, a personal ID verification system to be applied to gate control, for example, is disclosed. In the personal ID verification system, anl input fingerprint image is processed into binary image data and directional distributions of ridge lines are extracted and checked making use of mask patterns each having straight stripes ranged in different direction. Therefore, if the input fingerprint image is taken with a different position or different direction from those applied when the filed fingerprint is registered, the correct matching becomes difficult, which is usual in the case of a searching fingerprint gathered from a criminal field.
There is another stripe pattern matching method disclosed in a Japanese patent application laid open as a Provisional Publication No. 144982/'84. In this prior art, coincidence of ridge lines between a searching stripe pattern input through an image sensor and a filed stripe pattern is verified instead of matching of minutiae between the two stripe patterns. Therefore, correct matching cannot be obtained also in this prior art, when position or direction of the input searching stripe pattern differs from that of the filed stripe pattern. In this Provisional Publication, another method similar to the personal ID verification system of the Provisional Publication No. 183380/'90 is also proposed, wherein minutiae are extracted to be verified each time from the input searching stripe pattern referring to minutiae of the filed stripe pattern for confirming matching of the two stripe patterns. However, this method becomes also ineffective when position or direction of the input searching stripe pattern differs from that of the filed stripe pattern.
Furthermore, above two methods are, in practice, impossible to be applied to a fingerprint matching system used for criminal investigation, wherein filed fingerprints of more than 100 thousand persons are registered, for example. When 12 minutiae are to be checked for a fingerprint (it is said that two fingerprints can be regarded as those obtained from the same finger when 12 pairs of minutiae coincide between the two fingerprints.), and fingerprints of ten fingers are registered for a person, matching with more than a million filed fingerprints should be performed. It means that more than 12.times.1,000,000 minutiae must be extracted, which is extremely inefficient in practice.